class Solution {
public:
    using ull = unsigned long long;
    int mod = 100000007;
    int getHash(vector<ull>& hash,vector<ull>& mul,int l,int r){
        return hash[r+1] - hash[l] * mul[r-l+1];
    }
    int distinctEchoSubstrings(string text) {
        int ret = 0;
        unordered_set<ull> st;
        ull base = 31;
        vector<ull> hash(text.size()+1),mul(text.size()+1);
        hash[0] = 0;
        mul[0] = 1;
        
        for(int i = 1;i <= text.size();i++){
            hash[i] = hash[i-1] * base + text[i - 1];
            mul[i] = mul[i-1] * base;
        }
        
        for(int i = 0;i < text.size();i++){
            for(int j = i + 1;j < text.size();j++){
                int len = j - i + 1;
                
                if(len % 2 == 0){
                    ull hash_left = getHash(hash,mul,i,len/2+i-1);
                    
                    if(!st.count(hash_left) && getHash(hash,mul,i+len/2,j) == hash_left){
                        ret++;
                        st.insert(hash_left);
                    }
                }
                
            }
        }
        return ret;
    }
};
